\chapter{贪心算法}

\section{贪心算法}

\subsection{贪心算法（Greedy Algorithm）}

贪心算法，又称贪婪算法，是指在对问题求解时，总是做出在当前看来是最好的选择，也就是说不从整体最优上加以考虑。算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键在于贪心策略的选择。\\

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。\\

在利用贪心算法求解问题之前，必须需要清楚什么样的问题适合用贪心算法。一般而言，能够利用贪心算法求解的问题都会具备以下两点性质：

\begin{enumerate}
	\item 贪心选择：当某一个问题的整体最优解可通过一系列局部最优解的选择达到，并且每次做出的选择可以依赖以前做出的选择，但不需要依赖后面需要做出的选择。

	\item 最优子结构：如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。
\end{enumerate}

贪心算法的基本思路分为：

\begin{enumerate}
	\item 建立数学模型描述问题。
	\item 把求解的问题分成若干个子问题。
	\item 对每个子问题求解，得到子问题的局部最优解。
	\item 把子问题的局部最优解合成为原问题的解。
\end{enumerate}

\mybox{买卖股票的最佳时期}\\

给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算所能获取的最大利润。（提示：可以尽可能地完成更多的交易，但不能同时参与多笔交易，在再次购买前出售掉之前的股票）。\\

\textbf{示例}

输入：[7, 1, 5, 3, 6, 4]

输出：7

解释：在第2天（股票价格 = 1）的时候买入，在第3天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。随后，在第4天（股票价格 = 3）的时候买入，在第5天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
public static int maxProfit(int[] prices) {
    int profit = 0;
    for(int i = 0; i < prices.length - 1; i++) {
        if(prices[i] < prices[i + 1]) {
            profit += prices[i + 1] - prices[i];
        }
    }
    return profit;
}
\end{lstlisting}

\vspace{0.5cm}

\mybox{分发饼干}\\

有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有大小。每个孩子最多只能吃一个饼干，且只有饼干的大小大于等于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。\\

\textbf{示例1}

输入：children = [1, 2, 3], cookies = [1, 1]

输出：1

解释：有三个孩子和两块饼干，3个孩子的饥饿度分别是1, 2, 3。虽然有两块饼干，由于它们的大小都是1，只能让饥饿度是1的孩子满足。所以应该输出1。\\

\textbf{示例2}

输入：children = [1, 2], cookies = [1, 2, 3]

输出：2

解释：有两个孩子和三块饼干，2个孩子的饥饿度分别是1, 2。拥有的饼干数量和大小都足以让所有孩子满足。所以应该输出2。\\

因为饥饿度最小的孩子最容易吃饱，所以先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。\\

这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。因为需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序，这样就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个孩子可以吃饱。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
public static int distribute(int[] children, int[] cookies) {
    Arrays.sort(children);
    Arrays.sort(cookies);

    int child = 0;
    int cookie = 0;
    while (child < children.length && cookie < cookies.length) {
        if (children[child] <= cookies[cookie]) {
            child++;
        }
        cookie++;
    }
    return child;
}
\end{lstlisting}

\vspace{0.5cm}

\mybox{硬币找零}\\

假设硬币的面值分别为1元、5元、10元、25元和100元，有一个小店拥有各面值硬币数量无限个，顾客买东西之后需要给顾客找零，如何能够使找零的硬币个数最少？\\

\textbf{示例}

输入：36

输出：3

解释：找零[25, 10, 1]\\

为了尽量减少硬币的数量，首先得尽可能地多使用面值大的硬币，也就是优先使用大面值的硬币。

\vspace{-0.5cm}

\begin{lstlisting}[language=Python]
def get_min_coins(coins, price):
    solution = []
    
    for coin in reversed(coins):
        while price >= coin:
            solution.append(coin)
            price -= coin
    
    return solution
\end{lstlisting}

\newpage

\section{部分背包}

\subsection{部分背包（Knapsack）}

假设有一个小偷，背着一个容量为c的背包（最多可以放的物品重量不能超过c）。商店中一共有n种物品，每种物品i的重量和价值分别为$ w_i $和$ v_i $。如何选择物品放入背包才能使得总价值最大？\\

假设背包的容量为30，各类物品对应的重量和价格如下：

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			\textbf{物品}  & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} \\
			\hline
			\textbf{重量w} & 10         & 5          & 15         & 10         & 20         \\
			\hline
			\textbf{价值v} & 20         & 30         & 15         & 25         & 10         \\
			\hline
		\end{tabular}
	}
	\caption{物品信息}
\end{table}

对于背包问题，很显然它是满足最优子结构性质的，因为一个容量为c的背包问题必然包含容量小于c的背包问题的最优解。如果要使最终的价值最大，那么必定需要使得选择的单位中联的物品的价值最大。所以背包问题的贪心策略是优先选择单位重量价值最大的物品，当这个物品选择完之后，继续选择其它价值最大的物品。\\

\mybox{部分背包}

\begin{lstlisting}[language=Python]
class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
        self.unit_value = value / weight
    
    def __str__(self):
        return "Item(weight=%d, value=%d, unit_value=%.2f)" % (
            self.weight, self.value, self.unit_value
        )

def knapsack(items, capacity):
    items.sort(key=lambda x: x.unit_value, reverse=True)

    selected_items = []
    selected_weight = 0

    for item in items:
        if selected_weight + item.weight <= capacity:
            selected_weight += item.weight
            selected_items.append(item)
        else:
            portion = (capacity - selected_weight) / item.weight
            item.weight *= portion
            item.value *= portion
            selected_items.append(item)
            break

    return selected_items

items = [
    Item(10, 20),
    Item(5, 30), 
    Item(15, 15),
    Item(10, 25),
    Item(20, 10)
]
capacity = 30

selected_items = knapsack(items, capacity)
for item in selected_items:
    print(item)
\end{lstlisting}

\newpage

\section{贪心算法局限性}

\subsection{局限性}

贪心算法可以用来解决优化问题，与其他算法相比，贪心算法的最大优点是在大多数情况下易于实现且非常高效，但也存在一些问题。\\

贪心算法不能保证解是最佳的，因为它总是从局部出发，并没从整体考虑。尽管贪心算法给出了接近最优的解决方案，但它未能产生最优的解决方案。背包问题和旅行商问题是贪心算法无法产生最佳解决方案的问题示例。\\

当需要实时解决方案且近似答案足够好时，贪心算法最适用。显然，贪心算法可在确保产生最佳解决方案的同时最大程度地减少时间，因此更适用于需要较少时间的情况。\\

\subsubsection{硬币找零}

假设有1元、5元、11元这三种面值的硬币，给定一个找零金额，比如28元，最少使用的硬币组合是什么？\\

使用贪心算法可以得到结果为[11, 11, 5, 1]，总共是4个硬币。对于这个例子而言，4个硬币的确是最优解。但是假如找零是15元呢？使用贪心算法结果为[11, 1, 1, 1, 1]，共用了5个硬币，然而最优解是[5, 5, 5]，共3个硬币。硬币找零问题可以使用动态规划计算出最优解。\\

\subsubsection{0-1背包}

部分背包问题可以用贪心算法实现，是因为选择放入的物品可以进行拆分，即并不需要放入整个物品。与之对应的另一种背包问题为0-1背包问题，这个时候整个物品不可以拆分，只可以选择放入或者不放入。0-1背包问题用贪心算法并不能求得准确的解，需要用动态规划算法求解。\\

假设0-1背包的容量为8，物品的重量和价值分别为：

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			\textbf{物品}     & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} \\
			\hline
			\textbf{重量w}    & 2          & 3          & 4          & 5          \\
			\hline
			\textbf{价值v}    & 3          & 4          & 5          & 6          \\
			\hline
			\textbf{单位价值} & 1.5        & 1.33       & 1.25       & 1.2        \\
			\hline
		\end{tabular}
	}
	\caption{物品信息}
\end{table}

使用贪心算法会优先选择单位重量价值最高的物品，当拿完物品1和物品2后，背包剩余容量为8 - 2 - 3 = 3。由于物品不可拆分，背包无法装入物品3和物品4。最终总价值为3 + 4 = 7。\\

但是使用动态规划可以计算出最佳方案是选择物品2和物品4，最大价值为4 + 6 = 10。

\newpage